2020.11.20 模拟赛

$\text{T1}$

Subtask 1 40 pts

直接暴力模拟即可。

Subtask 2 100 pts

不难发现重要的只有 $A+B$ 和 $C$，而且可以发现 $A+B+C$ 是一个定值。然后你发现答案其实就是 $2^k\times C\pmod {A+B+C}$，快速幂即可。

$\text{T2}$

Subtask 1 & 2 30 pts

直接暴力应该是可以的。

Subtask3 50 pts

可以每次建一个图，原点往扑克连一条流量为 $1$ 的边，扑克往面值分别连一条流量为 $1$ 的边，面值往汇点连一条容量为 $1$ 的边。每次查询 $[l,r]$ 的话直接只把 $[l,r]$ 这段面值的点往汇点连边即可。

时间复杂度 懂得都懂。

Subtask4 10 pts

直接前缀和判断即可。

Subtask5 100 pts

将每个扑克的 $u,v$ 相连，不难看出是一个树的时候一定不能满足全都选出来，如果里面有环则一定可以满足全都能选出来。

于是问题就是判定一个区间对应的点里是否包含树，直接离线下来扫描线即可。

时间复杂度 $\Theta(n\log n)$。

$\text{T3}$

思路1:树状数组

我们考虑对于点$v$算出它的值那么就是:

$\sum_{t=1}^{i-1} (x_t-dis[u_t,v]\times k_t)$

$=\sum_{t=1}^{i-1} (x_t-(deep[v]-deep[u_t])\times k_t)$

$=\sum_{t=1}^{i-1} (x_t+deep[u_t]\times k_t)-deep[v]\times \sum_{t=1}^{i-1} k_t$

但是我们发现这个东西需要满足$u_t$在$1\to v$的路径上，怎么办呢？很简单，我们可以利用$dfs$的特性解决即可，然后这个东西直接用两个树状数组维护即可。

因为一个操作会加入删除各一次，所以总时间复杂度为$\Theta(m\log m+n)$。

思路2:线段树

其实很套路，我们发现这个东西是给子树内加上一个等差数列（不是很严谨，大家意会一下），跟这道题有些相似。

于是就十分套路了。我们直接用线段树维护一个差分数组，每次操作就相当于给$u$节点加上$x$,给子树内其他节点加上$-k$。

查询操作就相当于询问$1\to u$的路径和。

时间复杂度为$\Theta(m\log ^2n+n)$。

$\text{T4}$

Subtask 1

这个怎么暴力都可以吧

Subtask 2

还是暴力，加上记忆化就可以了。

因为 $m=2$ 好写很多。

Subtask 3 $~~~k=0$

$f_0(n)=\sum_{\prod p_i=n} [\forall i,j(i\not=j) \gcd(p_i,p_j)=1]$

令 $\tau(n)$ 为 $n$ 的不同质因数的个数。

因为要求任意 $p_i,p_j(i\not=j)$，$\gcd(p_i,p_j)=1$ ， 那么相同的质因数只会全部在其中一个 $p_i$中。

每种不同的质因数有 $m$ 种选法，那么 $f_0(n)=m^{\tau(n)}$

可以看出，$f_0(n)$ 是一个积性函数。

具体实现可以欧拉筛出最小质因子，对询问的 $n$ 分解质因数后将每一部分乘起来。

Subtask 4 $~~~k\not =0$

$f_k(n)=\sum_{\prod p_i=n} \prod f_{k-1}(p_i)$

因为 $f_0(n)$ 是一个积性函数，可以猜测 $f_k(n)$ 也是一个积性函数。

考虑数学归纳法：

1. $k=0$ 显然

2. $k\not=0$，假设 $f_{k-1}$ 为积性函数，对于任意互质两数 $n,m$ 有：

   $f_{k}(n) \times f_{k}(m) =\sum_{\prod p_i=n} \prod f_{k-1}(p_i) \times \sum_{\prod q_i=m} \prod f_{k-1}(q_i)$

   $~~~~~~~~~~~~~~~~~~~~~~~~~=\sum_{\prod p_i=n ,\prod q_i=m} \prod f_{k-1}(p_i) \times \prod f_{k-1}(q_i)$

   $~~~~~~~=\sum_{\prod p_i \prod q_i=nm} \prod f_{k-1}(p_i \times q_i)$

   $=f_k(nm)~~~~~~~~~~~~~~~~~~~~~~~~~$

现在只需要求出质数的幂的函数值即可。

$f_k(p^w)=\sum_{\sum p_i=w} \prod f_{k-1}(p^{p_i})$

发现 $f_k(p^w)$ 和 $p$ 的值无关，所以可以提取出一个递推式：

$f_{k,w}=\sum_{\sum p_i=w} \prod f_{r-1,p_i}$

这个我也不知道怎么递推，不过给了分的...

tr 巨佬提出了一个 $\mathcal O(km\log^2n)$ 的做法 ？

Subtask 5

发现 $f_0 = \{1,m,m....\}$ , $f_k=(f_0)^{m^k}$

观察每一项，发现除了第一项系数都为 $m$。

可以钦定 $m$ 的个数为 $i$ ，那么对系数的贡献便为 $m^i$

再考虑方案数，首先你得从 $m^k$ 个 $f_0$ 中选出 $i$ 个来提供指数，然后用插板法算出分配指数的方案。

答案为：

$f_{k,w}=\sum_{i=1}^w m^i \binom{m^k}{i} \binom{w-1}{i-1}$

这样单次询问可以暴力算组合数，是 $\mathcal O(\sum w)$ 的，比 $\mathcal O(\log n)$ 小。

瓶颈在于求 $m^k$ ，复杂度 $\mathcal O(q \log \text{mod})$

当然你用 ** 函数的知识会更好理解一些。